class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        lib = set(wordList)
        if len(beginWord) != len(endWord): return 0
        if endWord not in lib: return 0
        visited = set()
        visited.add(beginWord)
        queue = [(beginWord, 1)]
        while queue:
            word, cnt = queue.pop(0)
            cnt += 1
            for i in range(8):
                # 每次改变当前单词字符串的一位
                for char in "abcdefghijklmnopqrstuvwxyz":
                    next_ = word[:i] + char + word[i+ 1:]
                    if next_ not in visited and next_ in lib:
                        # next_单词没有处理过且在库里，是一个可转移的节点
                        if next_ == endWord:
                            return cnt
                        visited.add(next_)  # 下一个单词字符串入哈希表，表示已经入队了
                        queue.append((next_, cnt))
        return 0  